package algorithm.ordered_table;

import java.util.ArrayList;
import java.util.logging.Level;

public class SkipListMap {

    //从高层开始往右到不能再往右时开始往下跳，再往右到不能再往右时开始往下跳 ...
    //第0层包含所有的节点N，1层N/2个，2层N/4 ...，通过概率实现

    public static class SkipListNode<K extends Comparable<? super K>, V>{
        private K key;
        private V value;
        private ArrayList<SkipListNode<K, V>> nextNodes;

        public SkipListNode(K key, V value){
            this.key = key;
            this.value = value;
            nextNodes = new ArrayList<>();
        }

        //head头节点的key值比任何数都小
        public boolean isKeyLess(K otherKey){
            if(otherKey == null)
                return false;
            return this.key == null || this.key.compareTo(otherKey) < 0 ? true : false;
        }

        public boolean isKeyEqual(K otherKey){
            return this.key == null && otherKey == null ||
                    this.key != null && otherKey != null && this.key.compareTo(otherKey) == 0;
        }
    }

    public static class MySkipListMap<K extends Comparable<? super K>, V>{
        private static final double PROBABILITY = 0.5;
        private SkipListNode<K, V> head;
        private int maxLevel;
        private int size;

        public MySkipListMap(){
            head = new SkipListNode<>(null, null);
            head.nextNodes.add(null);//第0层存储所有的节点，注意一定要添加一个null
            maxLevel = 0;
            size = 0;
        }

        private SkipListNode<K, V> mostRightLessNodeInTree(K key){
            if(key == null) {
                return null;
            }
            int level = this.maxLevel;
            SkipListNode<K, V> cur = head;
            while(level >= 0){
                cur = mostRightLessNodeInLevel(key, cur, level--);
            }
            return cur;
        }

        private SkipListNode<K, V> mostRightLessNodeInLevel(K key, SkipListNode<K, V> cur, int level){
            SkipListNode<K, V> pre = cur;
            while(cur != null && cur.isKeyLess(key)){
                pre = cur;
                cur = cur.nextNodes.get(level);
            }
            return pre;
        }

        public boolean containKey(K key){
            if(key == null)
                return false;
            SkipListNode<K, V> cur = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = cur.nextNodes.get(0);
            return next != null && next.isKeyEqual(key);
        }

        public void put(K key, V value) {
            if (key != null) {
                SkipListNode<K, V> node = mostRightLessNodeInTree(key).nextNodes.get(0);
                if (node != null && node.isKeyEqual(key))
                    node.value = value;
                else {
                    this.size++;
                    int newLevel = 0;
                    while (Math.random() < PROBABILITY)
                        newLevel++;
                    while (newLevel > maxLevel) {
                        this.head.nextNodes.add(null);
                        maxLevel++;
                    }
                    SkipListNode<K, V> newNode = new SkipListNode<K, V>(key, value);
                    for (int i = 0; i <= newLevel; i++) {
                        newNode.nextNodes.add(null);
                    }
                    int level = this.maxLevel;
                    SkipListNode<K, V> cur = head;
                    while(level >= 0){
                        SkipListNode<K, V> rightNode = mostRightLessNodeInLevel(key, cur, level);
                        if(newLevel >= level){
                            newNode.nextNodes.set(level, rightNode.nextNodes.get(level));
                            rightNode.nextNodes.set(level, newNode);
                        }
                        level--;
                        cur = rightNode;
                    }
                }
            }
        }

        public void remove(K key){
            if(key != null && containKey(key)){
                this.size--;
                int level = this.maxLevel;
                SkipListNode<K, V> cur = head;
                while(level >= 0){
                    SkipListNode<K, V> rightNode = mostRightLessNodeInLevel(key, cur, level);
                    if(rightNode.nextNodes.get(level) != null && rightNode.nextNodes.get(level).isKeyEqual(key)){
                        rightNode.nextNodes.set(level, rightNode.nextNodes.get(level).nextNodes.get(level));
                        if(head.nextNodes.get(level) == null && level != 0){
                            head.nextNodes.remove(level);
                            maxLevel--;
                        }

                    }
                    cur = rightNode;
                    level--;
                }
            }
        }

        public V get(K key){
            if(key == null)
                return null;
            SkipListNode<K, V> rightNode = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = rightNode.nextNodes.get(0);
            return next == null ? null : next.isKeyEqual(key) ? next.value : null;
        }

        public K firstKey(){
            SkipListNode<K, V> first = head.nextNodes.get(0);
            return first == null ? null : first.key;
        }

        public K lastKey(){
            SkipListNode<K, V> cur = head;
            int level = maxLevel;
            while(level >= 0){
                while(cur.nextNodes.get(level) != null){
                    cur = cur.nextNodes.get(level);
                }
                level--;
            }
            return cur.key;
        }


    }

    public static void printAll(MySkipListMap<String, String> obj) {
        for (int i = obj.maxLevel; i >= 0; i--) {
            System.out.print("Level " + i + " : ");
            SkipListNode<String, String> cur = obj.head;
            while (cur.nextNodes.get(i) != null) {
                SkipListNode<String, String> next = cur.nextNodes.get(i);
                System.out.print("(" + next.key + " , " + next.value + ") ");
                cur = next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MySkipListMap<String, String> test = new MySkipListMap<>();
        printAll(test);
        System.out.println("======================");
        test.put("A", "10");
        printAll(test);
        System.out.println("======================");
        test.remove("A");
        printAll(test);
        System.out.println("======================");
        test.put("E", "E");
        test.put("B", "B");
        test.put("A", "A");
        test.put("F", "F");
        test.put("C", "C");
        test.put("D", "D");
        printAll(test);
        System.out.println("======================");
        System.out.println(test.containKey("B"));
        System.out.println(test.containKey("Z"));
        System.out.println(test.firstKey());
        System.out.println(test.lastKey());
        System.out.println("======================");
        test.remove("D");
        printAll(test);
    }
}
